1. Field of the Invention
The present invention relates generally to a method of controlling an execution of a data flow program in information processor and an apparatus therefor, and more particularly, to a method of controlling execution of a data flow program for processing array type data and an apparatus therefor.
2. Description of the Background Art
In a conventional von Neuman computer, various instructions are stored as a program in a program memory in advance, and addresses in the program memory are sequentially specified by a program counter so that the instructions are sequentially read out, whereby instructions are executed.
On the other hand, a data driven type information processor is one type of non-vonNeuman computers which do not use the concept of sequential execution of instructions by a program counter. Such data driven type information processor an architecture based on parallel processing of instructions. In the data driven type information processor execution of an instruction is enabled upon collection of data to be operated, and a plurality of instructions are simultaneously driven by data, so that programs are executed in parallel in accordance with a natural flow of the data. As a result, the time required for the operation will be drastically reduced.
FIG. 13 is a schematic diagram showing the structure of a data driven type information processor to be applied to a conventional example and one embodiment of the present invention. FIG. 14 shows a field structure of a data packet circulating through the data driven type information processor to be applied to a conventional example and an embodiment of the present invention.
In FIG. 14, a data packet PA includes a destination field F1 for storing destination information including branch information, an instruction field F2 for storing instruction information, a data 1 field F3 and a data 2 field F4 for storing operand data.
With reference to FIG. 13, a data driven type information processor 1 is connected to a data packet generation/supply unit 8. Externally provided to the main body of a processing unit of information processor 1 are an extended data storage unit 2 and an extended program storage unit 7 having a large capacity and a low access rate. The main body of tile processing unit of information processor 1 further includes an input/output control unit 3, a program storage unit 4 having a small capacity and a high access rate for storing a data flow program to be executed, a firing control unit 5 which has a queuing memory 51 and serves for detecting paired data, and an operation unit 6.
Data packet generation/supply unit 8 includes a load packet processing portion 81 for loading a program to be executed or data to be processed in accordance with the program in the information processor prior to execution of the program at information processor 1, and a packet for execution processing portion 82 for supplying data to be processed during program execution to information processor 1. Load packet processing portion 81 loads the program or the data in the form of data packets 20P and 21P to information processor 1, while packet for execution processing portion 82 supplies data to be processed in the form of a data packet 22P to information processor 1. Details of such data packets will be described later.
Extended program storage unit 7 functions as an extended storage device related to a data flow program to be executed by information processor 1. Storage unit 7 receives a data packet PA to carry out initial writing of program data by using the received packet PA at the program loading, and reads the program data by addressing based on destination information in a data packet PA applied from firing control unit 5, stores the read data into a data packet and outputs the data packet to program storage unit 4 when the program is executed.
FIG. 15 shows a structure of the extended data storage unit 2 in block. Extended data storage unit 2 functions as an extended storage device related to data to be processed in accordance with the data flow program at information processor 1. FIG. 16A and 16B show field structures of a data packet for use in accessing extended data storage unit 2. A data packet 10P of FIG. 16A stores an access instruction ACC for accessing the extended data storage unit 2 in a field F2, stores address information AD related to an instruction ACC in a field F3 and stores write data WD to be written in extended data storage unit 2 in a field F4 when the instruction ACC indicates a writing instruction. A data packet 10P' of FIG. 16, which is a data packet for storing resultant data obtained by accessing extended data storage unit 2 by using data packet 10P, stores, when the access instruction ACC in the corresponding data packet 10P indicates data reading from extended data storage unit 2, the read data RD in a field 73.
With reference to FIGS. 15, 16A and 16B, extended data storage unit 2 will be described.
Extended data storage unit 2 includes a memory 21 for storing data, an instruction decoding portion 22, an access portion 23 including an address storage portion 231, and a packet output portion 24. Extended data storage unit 2 receives data packets 20P and 21P as will be described later from input/output control unit 3 and writes (loads) data stored in the received data packets in memory 21 prior to an execution of the program at information processor 1. Storage unit 2 receives data packet 10P from input/output control unit 3, accesses memory 21 based on information in the received data packet and outputs data packet 10P or 10P' storing access resultant data to input/output control unit 3 during the program is executed. More specifically, input/output control unit 3 applies data packet 10P to instruction decoding portion 22. Decoding portion 22 receives the applied data packet 10P and applies the same packet to output portion 24 while decoding an access instruction ACC in field F2 of the received packet. When the access instruction ACC indicates a writing instruction as a result of the decoding, decoding portion 22 instructs access portion 23 on a writing operation and applies the received packet to access portion 23, and conversely, when the instruction ACC indicates a reading instruction, decoding portion 22 instructs access portion 23 on a reading operation and applies the received packet to access portion 23. Access portion 23 receives the data packet applied from decoding portion 22, addresses memory 21 based on address information AD in the received packet in response to an instruction of a writing operation by decoding portion 22 and writes write data WD of the received packet in an addressing area of memory 21. Conversely, in response to an instruction of a reading operation by decoding portion 22, access portion 23 reads data from memory 21 by addressing based on the address information AD in the received packet. Access portion 23 informs packet output portion 24 of the end of access at the completion of the access to memory 21 and applies data read from memory 21. Packet output portion 24, when it is informed of the end of the access by access portion 23 and supplied with the read data, stores the responsively read data as read data RD in the field F3 of data packet 10P applied from decoding portion 22 and outputs the packet as a data packet 10P' to input/Output control unit 3. When the packet output portion is only informed of the end of the access by access portion 23, it outputs data packet 10P applied from decoding portion 22 to input/output control unit 3. Details of address storage portion 231 will be described later.
With reference to FIG. 13, input/output control unit 3 receives a data packet PA applied from the outside (data packet generation/supply unit 8) information processor 1, and from extended data storage unit 2 and operation unit 6 and selectively outputs the received data packet PA to the outside information processor 1, or to extended data storage unit 2 or to program storage unit 4.
FIG. 17 shows a part of the data flow program to be stored in program storage unit 4. Program storage unit 4 stores a data flow program including a plurality of pairs of designation information, instruction information and copy presence/absence informations shown in FIG. 17. Program storage unit 4 receives a data packet PA applied from input/output control unit 3, reads destination information, instruction information, and copy presence/absence information in a subsequent order from the data flow program by addressing based on destination information in the received packet PA, stores the read destination information and instruction information in a destination field F1 and an instruction field F2 of the received packet PA, respectively, and applies the packet PA to firing control unit 5. When the read copy presence/absence information indicates "absence" at this time, a data packet with the contents in destination field F1 and instruction field F2 updated is output to complete a processing. On the other hand, when the read copy presence/absence information indicates "presence", a data packet with the contents of the destination field and the instruction field updated is output, and subsequently stored destination information, instruction information and copy presence/absence information are read out. When the subsequently read out copy presence/absence information indicates "absence", a data packet is output to complete the processing which stores the same data as that of the received data packet in its data 1 field F3 and the currently read out destination information and instruction information in its destination field F1 and its instruction field F2, respectively. If the subsequently read out copy presence/absence information indicates "presence", the same copy processing is further continued.
Program storage unit 4 receives a data packet PA storing program data read out from extended program storage unit 7 and stores tile program data stored in the received packet PA.
FIG. 18 shows a part of the storage contents of queuing memory 51 in firing control unit 5 of FIG. 13. With reference to FIG. 18, queuing memory 51 stores a plurality of queuing operand data. Fizzing control unit 5 sequentially receives data packets PA applied from program storage unit 4, detects two different data packets PA having the same destination information, stores operand data of one of the data packets PA, for example, the contents of data 1 field, in data 2 field of the other data packet and outputs (hereinafter referred to as "firing") said the other data packet PA. More specifically, firing control unit 5 accesses queuing memory 51 by addressing based on destination information in an applied packet PA and if storage of queuing operand data is detected by the accessing, firing control unit 5 stores the queuing operand data in data 2 field F4 of the applied packet PA and outputs the packet PA. If the queuing operand data is not stored, the firing control unit writes operand data of data 1 field F3 of the applied packet PA in a corresponding addressing area of memory 51. As a result, the applied packet PA is to queue an input of a data packet to be paired. Firing control unit 5 performs the above-described firing detection processing if instruction information in the applied packet PA is a 2-operand instruction, while the unit Outputs the applied data packet PA without being operated if the instruction information is a 1-operand instruction.
Operation unit 6 of FIG. 13 receives a data packet PA applied from firing control unit 5, performs an operation processing for operand data stored in the applied packet PA based on instruction information stored in the applied packet PA, stores the operation resultant data in data 1 field or data 2 field of the applied data packet PA and outputs the applied packet
to input/output control unit 3.
In data driven type information processor 1 of FIG. 13, data packets storing a data flow program are applied from data packet generation/supply unit 8 to information processor 1 and stored in program storage unit 4 and extended program storage unit 7 prior to an execution of the data flow program. The applied program data are all stored in extended program storage unit 7, while initial program data, for example, a program data group of initial 1K words, of the applied program data, are also stored in program storage unit 4.
FIGS. 19A to 19C are diagrams showing field structures of a data packet supplied from data packet generation/supply unit 8 to information processor 1. When loading of the program data is completed in a manner as described-above, data to be processed in accordance with the program is loaded in extended data storage unit 2 prior to an execution of the loaded program. At the time of the data loading, data packet generation/supply unit 8 applies data packets 20P and 21P respectively shown in FIGS. 19A and 19B to input/output control unit 3. Data packet generation/supply unit 8 first applies data packet 20P to input/output control unit 3, whereby input/output control unit 3 applies data packet 20P to extended data storage unit 2 in response to the branch information of data packet 20P indicating that the information is destined for data storage unit 2. Instruction decoding portion 22 of extended data storage unit 2 receives a data packet 20P and in response to instruction information in the received packet 20P indicating a load instruction LD, instructs access portion 23 on data loading and applies data packet 20P to access portion 23. Access portion 23 receives data packet 20P and temporarily stores in address storing portion 231 a start address and an end address stored in fields F3 and F4 of packet 20P. The start address and the end address are data for specifying an area on memory 21 where data applied hereafter is to be stored. Data packet generation/supply unit 8 outputs data packet 21P of FIG. 19B subsequent to data packet 20P. Input/output control unit 3 receives data packet 21P and in response to branch information in the received packet 21P indicating that the information is destined for data storage unit 2, applies the received packet 21P to extended data storage unit 2. Instruction decoding portion 22 of extended data storage unit 2 receives the data packet 21P and decodes instruction information in packet 21P as a loading instruction LD to instruct access portion 23 on data loading and apply packet 21P to the portion 23. Access portion 23 writes the contents of field F3 of packet 21P in an area of memory 21 specified by a start address and an end address in address storage portion 231. Successive supply of a plurality of data packets 21P to information processor 1 by data packet generation/supply unit 8 stores a plurality of data in an area of memory 21 specified by a start address and an end address in address storage portion 231, resulting in completion of data loading in information processor 1. Data loading in extended data storage unit 2 may be performed prior to the above-described program loading. The information processor is regardless of the order of loading of the program and the data.
Processing in accordance with the program is executed at the completion of loading the program and the data in data driven type information processor 1. First, data packet generation/supply unit 8 applies a data packet 22P shown in FIG. 19C to information processor 1. A destination field F1 of data packet 22P stores branch information indicating that the packet is destined for program storage unit 4, a field F2 stores an execution instruction EX for executing the program and a field F3 stores data. Input/output control unit 3 receives an applied data packet 22P and provides the received packet 22P to program storage unit 4 based on the branch information in packet 22P. Program storage unit 4 reads out destination information and instruction information in a subsequent order by addressing based on the destination information in the received packet 22P. The read out information are respectively stored in fields F1 and F2 of the received packet 22P and the packet is applied to firing control unit 5. Firing control unit 5 performs a processing for detecting firing as described above. A data packet obtained by a firing detection is applied to operation unit 6. Operation unit 6 performs an operation processing with respect to the applied data packet and outputs a data packet which stores the operation resultant data. Input/output control unit 3 receives a data packet applied from operation unit 6 and outputs the data packet to one of the program storage unit 4, outside information processor 1 or extended data storage unit 2 based on the branch information in the received packet. When the data packet is provided to program storage unit 4, destination information and instruction information in a further subsequent order are to be read out. On the other hand, when the data packet is provided to extended data storage unit 2, such access related to memory 21 as described with reference to FIG. 15 is performed and a data packet storing the access resultant data is selectively output to program storage unit 4 or outside information processor 1 through input/output control unit 3.
As a data packet continues to circulate through input/output control unit 3.fwdarw.program storing unit 4.fwdarw.firing control unit 5.fwdarw.operation unit 6.fwdarw.input/output control unit 3.fwdarw. . . . as described in the foregoing, an operation processing proceeds based on the program and the data stored in program storage unit 4, extended program storage unit 7 and extended data storage unit 2.
Since extended data storage unit 2 has a large capacity but a low access rate in the above-described data driven type information processor, it is preferable to selectively use the storage unit 2 and an internal memory of information processor 1 in order to increase a program's processing rate. For example, data which is frequently accessed is stored in program storage unit 4 or queuing memory 51 both of which have an access rate higher than that of extended data storage unit 2, while data, which is less frequently accessed is stored in extended data storage unit 2. Data stored in extended data storage unit 2 will be referred to as memory data and data flowing as a data packet PA on a transmission path inside the data driven type information processor 1 will be referred to as flow data hereinafter.
Some data processed in accordance with a data flow program are of an array type. An array is a group of data put in an order in one of one-dimensional, two-dimensional, three-dimensional manners and uniquely identified by an English name. The English name is referred to as an array name, one of the data constituting the array is referred to as an array element and an English name for uniquely identifying the element as an array element name. Array type data to be processed in accordance with a data flow program are all processed as memory data. An array to be processed in accordance with the data flow program, for example, a one-dimensional array, will be represented as ar[I] (I=0, 1, 2, 3, . . . n). The array ar[I] indicates that the array name is "ar" and the array element name is "I". The array ar[I] itself is treated as memory data to be stored in memory 21 of extended data storage unit 2, while the array element is treated as flow data. Therefore, by storing a group of data constituting the array ar[I] in memory 21 of storage unit 2 in advance and applying to storage unit 2 a data packet 10P storing the array element name I as address information AD, memory 21 is accessed by addressing based on the array element name I at storage unit 2 to read/write data ar[I]. However, since extended data storage unit 2 is a low-speed access memory, when array type data is used as memory data, a rate of processing the array type data is limited by the access rate of the extended data storage unit 2.
The above-described limitation of the array type data processing rate can be eliminated by treating the array ar[I] itself as flow data similarly to an array element, for which the array ar[I] itself and the array element name should be synchronized with each other. The synchronization is obtained as follows. First, data ar[1], ar[2], . . . ar[n] constituting the array ar[I] are made into data packets PA at data packet generation/supply unit 8 and supplied to data driven type information processor 1. The supplied data packets are applied to firing control unit 5 through input/output control unit 3 and program storage unit 4 to wait for an input of a corresponding array element name I as queuing operand data at queuing memory 51. Thereafter, the program starts to be executed. When a data packet storing an array element name I defined, for example, as 3 in its destination field F1 is applied to firing control unit 5 during the execution, firing is detected to output a data packet storing data ar[3], resulting in synchronization between the array ar[I] itself and the array element name I. It is commonly known that synchronization between data packets PA in a data driven type information processor causes a processing time loss. In other words, a processing time loss is a sum of times for all data ar[1], ar[2] . . . ar[n] constituting the array ar[I] to wait for firing at queuing memory 51 of firing control unit 5.
Another disadvantage is that since all the data ar[1], ar[2], . . . ar[n] constituting the array ar[I] should be made to stand by at queuing memory 51 until an element name I as flow data is defined during the program execution, an extremely large flow graph corresponding to the data flow program is required. Such disadvantage will be described as follows. FIG. 20 is a diagram schematically showing a data flow program development procedure. FIG. 21 is a block diagram showing functions of a compiler related to a conventional data flow program, while FIG. 22 is a block diagram showing functions of a mapper related to the data flow program. FIGS. 23A to 23C are diagrams showing examples of a flow graph obtained by replacing a data flow program for processing array type data. FIGS. 24A to 24D are diagrams showing examples of a data flow program and examples of a flow graph obtained by compiling the program.
As shown in FIG. 20, a data flow program development procedure is made up of a text editor 100, a flow graph compiler 200, a flow graph linker 300 and a mapper 400, functions of which are prepared as software by a work station and the like. First, a data flow program 111 is created through an edition processing by the text editor 100. The data flow program 111 is described based on the C language proposed by the present applicant by using parallel processing language (hereinafter referred to as FGCL: FGCL is an abbreviation of a flow graph C language) with description for data drive added. Flow graph compiler 200, flow graph linker 300 and mapper 400 are processing systems suitable for FGCL. Thorn, the data flow program 111 is subjected to grammatical analysis by flow graph compiler 200 and developed into a plurality of flow graphs having a structure showing data flows on the program in parallel. Flow graph compiler 200 includes a syntax analysis step 201, a flow graph development step 202 and a rank analysis step 203 as shown in FIG. 21. Input data of flow graph compiler 200 is a program 111 described in FGCL. In syntax analysis step 201, the data flow program 111 is applied to see if the description contents of the program 111 match the grammar of FGCL and then in flow graph development step 202, the data flow program 111 is developed into a plurality of flow graphs in parallel in accordance with the contents of the grammar analysis. In rank analysis step 203, the plurality of flow graphs obtained by the development are rearranged to operate in accordance with the order of execution of instructions and the arranged flow graphs are sent to flow graph linker 300. Flow graph linker 300 receives the plurality of flow graphs 211 applied from flow graph compiler 200, groups the flow graphs together into one processable flow graph 311 at information processor 1 and applies the flow graph 311 to mapper 400. Mapper 400 makes the applied flow graph 311 into an object file 411 and an input packet file 412 which are applied to a load packet processing portion 81 and a packet for execution processing portion 82 in data packet generation/supply unit 8 as a target system, respectively. Object file 411 includes a program to be loaded in information processor 1 and initial value data to be loaded in extended data storage unit 2, while input packet file 412 stores information for generating a packet to be applied to information processor 1. Load packet processing portion 81 generates a data packet storing a program and data to be loaded in information processor 1 based on data in object file 411 and packet for execution processing portion 82 generates based on information in input packet file 412, a data packet, for example, to be supplied to information processor 1 while the processor 1 executes the program. Mapper 400 includes step 401 of generating program data to be loaded, a step 402 of generating data to be loaded in storage unit 2 and a step 403 of generating information for use in generating a packet to be supplied to information processor 1 as shown in FIG. 22. In steps 401 to 403, flow graph 311 is input to output object file 411 and input packet file 412. Hereinafter, a flow graph compiler is abbreviated as a compiler.
In compiler 200, the data flow programs shown in FIGS. 24A and 24C, for example, are compiled to be developed into flow graphs of FIGS. 24B and 24D. The two flow graphs are converted by flow graph linker 300 into one flow graph by applying flow graph of FIG. 24D to the part of "funcl" of FIG. 24B.
Compiler 200 complies the array A[I] in the data flow program in a manner as shown in FIGS. 23A to 23C. If an element name I is not defined at a stage of compiling, for example, it is necessary to simultaneously queue data A[1], A[2], . . . A[n] at queuing memory 51. The data A[1], A[2], . . . A[n] are therefore developed in parallel into flow data on the flow graph as shown in FIG. 23A. When the element name I is defined during the execution of the program, the element name I is synchronized (corresponding to sync in FIG. 23A) with data A[I] queuing in memory 51 to detect firing, causing only a data packet storing the data A[I] to flow as flow data. For example, when the element name I is defined as "1" during the execution of the program, only data A[1] selectively flows down the flow graph among the data A[1]-A[n] developed in parallel in the flow graph. In other words, firing is detected by firing control unit 5 of FIG. 13 to output an obtained data packet to operation unit 6.
Conversely, if the element name I is already as defined "3", for example, at a stage of edition of the data flow program 111 by text editor 100, compiler 200 compiles data A[3] in the program 111 as one flow data as shown in FIG. 23C. In other words, the element name I in the data flow program will not be developed into flow data in the flow graph by compiler 200 in this case.
As described in the foregoing, when the element name I is not defined at the time of compiling by compiler 200, all of the supposed data A[1]-A[n] are developed in parallel by the compiler. Therefore, the flow graph obtained by the development (see FIG. 23A) inevitably becomes much larger than the flow graph (see FIG. 23C) obtained by developing the data with the element name already defined at the time of compiling. Thus, if an array is treated as flow data in order to eliminate a limitation in a processing rate as described above, synchronization between an element name and data increases processing time loss and makes the flow graph larger in scale. Therefore, although a processing rate is limited, a program execution controlling method is employed wherein all of array type data are stored in extended data storage unit 2 and treated as memory data.
However, there is a case where an element name I of an array described in the program is already defined at a stage prior to compiling, depending on the contents of a processing expressed by using the data flow program. In other words, there is a case where an element name I is fixed and not be changed during execution of the data flow program. An array whose element name is not changed during execution of the program is hereinafter referred to as a static array and conversely, an array whose element name is changed during an execution of the program is referred to as a dynamic array. For example, such program description as I=3: b=ar[I]: means that an array ar[I] is a static array and its value is already defined as data ar[3] prior to compiling. In such a case, the element name I is data other than memory data and flow data. The compiler can therefore develop the program description into a flow graph as shown in FIG. 23C at the stage of compiling the data flow program including the description. As described in the foregoing, although some arrays to be processed in accordance with a program can be processed as flow data, a conventional method of controlling execution of a data flow program uniformly processes array type data as memory data, resulting in a decrease of a processing rate of information processor 1 more than required and preventing an effective use of a memory.